package morris

import "fmt"

func MorrisIn(head *Node){
	cur := head
	//fmt.Println(cur)
	for cur != nil {
		if cur.Left != nil {
			mostRight := GetMostRight(cur.Left, cur)
			if mostRight.Right == cur {
				mostRight.Right = nil
				fmt.Println(cur.Val)
				cur = cur.Right
			} else if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
			}
		} else {
			fmt.Println(cur.Val)
			cur = cur.Right
		}
	}
}

func MorrisIn1(head *Node){
	cur := head
	var mostRight *Node
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				// 能回到自己两次的节点 continue 不打印
				continue
			} else {
				mostRight.Right = nil
			}
		}
		// 每次向右移动就打印
		fmt.Println(cur.Val)
		cur = cur.Right
	}

}